快速排序

1. 算法思想：分治法，比大小再分区。
2. 过程：
   1. 从数组中选出一个数，作为基准数。
   2. 分区：将比这个数大或等于的数全放到他的右边，小于他的数全放到他的左边。
   3. 再对左右区间重复第二步，直到各区间只有一个数。

public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {10, 3, 5, 6, 1, 0, 100, 40, 50, 8};
        System.out.println(Arrays.toString(quickSort(arr, 0, arr.length - 1)));
    }

    private static int[] quickSort(int[] arr, int start, int end) {
        if (start < end) {
            // 获取基准数索引
            int index = getIndex(arr, start, end);
            // 左右递归
            quickSort(arr, start, index - 1);
            quickSort(arr, index + 1, end);

        }
        return arr;
    }

    private static int getIndex(int[] arr, int start, int end) {
        int i = start;
        int j = end;
        // 基准数
        int x = arr[i];
        while (i < j) {
            // 基准数右边排序
            while (i < j && arr[j] >= x) {
                j--;
            }
            if (i < j) {
                arr[i] = arr[j];
                i++;
            }

            //基准数左边排序
            while (i < j && arr[i] < x) {
                i++;
            }
            if (i < j) {
                arr[j] = arr[i];
                j--;
            }
        }

        // i=j
        return i;
    }

}